public class AddInList {
    // 链表相加II
    // https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        ListNode newHead1 = reverseList(head1);
        ListNode newHead2 = reverseList(head2);
        ListNode pHead = new ListNode(-1);
        ListNode cur = pHead;
        ListNode cur1 = newHead1;
        ListNode cur2 = newHead2;
        int tmp = 0;
        while (cur1 != null || cur2 != null || tmp != 0) {
            int num1 = cur1 == null ? 0 : cur1.val;
            int num2 = cur2 == null ? 0 : cur2.val;
            int sum = num1 + num2 + tmp;
            ListNode newNode = new ListNode(sum % 10);
            cur.next = newNode;
            tmp = sum / 10;
            cur = cur.next;
            cur1 = cur1 == null ? null : cur1.next;
            cur2 = cur2 == null ? null : cur2.next;
        }
        return reverseList(pHead.next);
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(9);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(7);
        node1.next = node2;
        node2.next = node3;
        node3.next = null;
        ListNode node4 = new ListNode(6);
        ListNode node5 = new ListNode(3);
        node4.next = node5;
        node5.next = null;
        System.out.println(new AddInList().addInList(node1, node4));
    }
}
